package com.lecode.LFU;

import java.util.HashMap;
import java.util.LinkedHashSet;

/**
 * Created by Administrator on 2020/8/15.
 *
 * LFU:最近最少未使用
 */
public class LFUCache {

    /**key  -  val*/
    HashMap<Integer, Integer> keyToVal;
    /**key - fre频次*/
    HashMap<Integer, Integer> keyToFreq;
    /**fre - key*/
    HashMap<Integer, LinkedHashSet<Integer>> freToKey;
    /**最小频次*/
    int minFre;
    /**容量*/
    int cpa;

    public LFUCache(int cpa){
        this.cpa = cpa;
        this.minFre = 0;
        keyToFreq = new HashMap<Integer, Integer>();
        keyToVal = new HashMap<Integer, Integer>();
        freToKey = new HashMap<Integer, LinkedHashSet<Integer>>();
    }

    /**
     * 获取元素，并将元素fre+1，最近使用
     * @param key
     */
    public Integer get(Integer key){
        if (!keyToVal.containsKey(key)){
            return -1;
        }
        /**key频次加一， 更新对于的映射表*/
        increase(key);
        return keyToVal.get(key);
    }

    public void increase(Integer key){
        int oldFre = keyToFreq.get(key);
        //更新key - fre映射
        keyToFreq.put(key, oldFre + 1);
        freToKey.get(key).remove(key);
        freToKey.putIfAbsent(oldFre + 1, new LinkedHashSet<Integer>());
        freToKey.get(oldFre + 1).add(key);
        if (freToKey.get(oldFre).isEmpty()){
            freToKey.remove(oldFre);
            if (oldFre == this.minFre){
                this.minFre++;
            }
        }
    }

    public void put(Integer key, Integer value){
        /**key存在*/
        if (keyToVal.containsKey(key)){
            keyToVal.put(key, value);
            increase(key);
            return;
        }

        /**容量已满*/
        if (this.cpa <= keyToVal.size()){
            removeMinFreqKey();
        }

        keyToVal.put(key, value);
        keyToFreq.put(key, 1);

        freToKey.putIfAbsent(1, new LinkedHashSet<Integer>());
        freToKey.get(1).add(key);
        /**将最小频次设置为1*/
        this.minFre = 1;
    }


    /**
     * 删除频次最少，时间最久的key
     */
    public void removeMinFreqKey(){
        LinkedHashSet<Integer> linkedHashSet = freToKey.get(this.minFre);
        Integer deleteKey = linkedHashSet.iterator().next();
        linkedHashSet.remove(deleteKey);
        if (freToKey.get(this.minFre).isEmpty()){
            freToKey.remove(this.minFre);
        }
        keyToVal.remove(deleteKey);
        keyToFreq.remove(deleteKey);
    }
}
